package _1_单调栈

/**
原题链接:
https://leetcode.cn/problems/daily-temperatures/

739. 每日温度
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，
其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

思路:
本题为最直接明了的单调栈题目, 单调栈就是用于求当前元素, 左面或者右面, 第一个比当前元素大或者小的元素
本题栈中直接存储元素的下标.
		这里模拟单调栈:
						----------------
					1	0				|
					74	73				|  栈底
						----------------

那么单调栈中保持元素递增还是递减呢? (栈口到栈底的方向)
	如果是递增的, 求得就是当前这个元素后面或者左边, 第一个比它大的元素
	如果是递减的, 求的就是当前这个元素后面或者左边, 第一个比它小的元素
	理解: 要理解为要放进来的元素, 打破单调栈的单调性, 然后产生结果计算


单调栈的作用:
存放已经遍历过的元素, 因为遍历数组元素O(n), 只有一个for循环, 但是并不知道之前已经遍历了哪些元素,
所以无法判断当前元素是否比之前的元素大, 这就需要有一个数据结构记录之前遍历过的元素, 用记录过的元素和当前元素做对比

那单调栈的存储方式肯定跟普通数组有区别, 就是放入时, 需要跟栈口的元素作比较, 那么就有三种情况:
	1.T[i] > T[st.top()]: 当前元素大于栈口元素
		如上图情况, 当前元素 > 栈口元素, 那么栈口元素要找到第一个比自己大的元素就找到了, 进行下标求差即可
		并且将栈口元素剔除, 因为已经计算出了结果, 栈中存放的是遍历过的,但是还没有等待符合自己条件的元素
		然后将74元素放入栈中即可
	2.T[i] < T[st.top()]: 当前元素小于栈口元素
		符合单调栈的单调性, 直接放入栈中, 等待符合自己条件的首个元素出现即可
	3.T[i] == T[st.top()]: 当前元素等于栈口元素
		本题是求第一个比当前元素大的, 所以直接放入栈即可

*/

func dailyTemperatures(temperatures []int) []int {
	ans := make([]int, len(temperatures)) //声明结果数组
	var stack []int                       //声明单调栈

	for curIndex, curVal := range temperatures { //遍历参数数组
		//栈不为空, 并且当前元素值,大于栈口元素的值
		for len(stack) > 0 && curVal > temperatures[stack[len(stack)-1]] {
			topIndex := stack[len(stack)-1] //栈顶元素的下标值
			stack = stack[:len(stack)-1]    //将栈顶元素剔除

			ans[topIndex] = curIndex - topIndex
		}

		stack = append(stack, curIndex)
	}

	return ans
}
